for
loop from Pascal:for I := 1 to 10 do <some statement>;When learning Pascal you were probably taught that this statement initializes
i with one, compares i with 10, and executes the
statement if i is less than or equal to 10. After executing
the statement, the for statement increments i
and compares it with 10 again, repeating the process over and over again
until I is greater than 10. for loop, this is
not the only point of view that describes how the for loop
operates. Suppose, instead, that you were to treat the "to"
reserved word as an operator. An operator that expects two parameters (one
and ten in this case) and returns the range of values on each successive
execution. That is, on the first call the "to" operator
would return one, on the second call it would return two, etc. After the
tenth call, the "to" operator would fail which would
terminate the loop. This is exactly the description of an iterator.foreach variable in iterator() do statements; endfor;
Variable is a variable whose type is compatible with the return
type of the iterator. An iterator returns two values: a boolean
success or failure value and a function result. As long as the iterator
returns success, the foreach statement assigns the other return
value to variable and executes statements. If
iterator returns failure, the foreach loop terminates and executes
the next sequential statement following the foreach loop's
body. In the case of failure, the foreach statement does not
affect the value of variable. Range:iterator(start,stop:integer):integer;
begin range;
while (start <= stop) do
yield start;
start := start + 1;
endwhile;
end Range;
In the Panacea programming language, iterator calls may only appear in the
foreach statement. With the exception of the yield statement above, anyone
familiar with Pascal or C++ should be able to figure out the basic logic
of this iterator.end Range; statement or it may yield a value by
executing the yield statement. An iterator succeeds if it executes
the yield statement, it fails if it simply returns to the caller.
Therefore, the foreach statement will only execute its corresponding
statement if you exit an iterator with a yield. The foreach
statement terminates if you simply return from the iterator. In the example
above, the iterator returns the values start..stop via a yield
and then the iterator terminates. The loop foreach i in Range(1,10) do
write(i);
endfor;
is comparable to the Pascal statement:for i := 1 to 10 do write(i);When a Panacea program first executes the
foreach statement,
it makes an initial call to the iterator. The iterator runs until it executes
a yield or it returns. If it executes the yield
statement, it returns the value of the expression following the yield
as the iterator result and it returns success. If it simply returns, the
iterator returns failure and no iterator result. In the current example,
the initial call to the iterator returns success and the value one.foreach
statement assigns the iterator return value to the loop control variable
and executes the foreach loop body. After executing the loop
body, the foreach statement calls the iterator again. However,
this time the foreach statement resumes the iterator rather than making
an initial call. An iterator resumption continues with the first statement
following the last yield it executed. In the range
example, a resumption would continue execution at the start := start
+ 1; statement. On the first resumption, the Range iterator
would add one to start, producing the value two. Two is less
than ten (stop's value) so the while loop would
repeat and the iterator would yield the value two. This process would repeat
over and over again until the iterator yields ten. Upon resuming after yielding
ten, the iterator would increment start to eleven and then return, rather
than yield, since this new value is not less than or equal to ten. When
the range iterator returns (fails), the foreach
loop terminates. push 1 ;Assume 286 or better
push 10 ; and parms passed on stack.
call Range_Initial ;Make initial call to iter.
jc Failure ;C=0, 1 means success, fail.
ForLoop: puti ;Assume result is in AX.
call Range_Resume ;Resume iterator.
jnc ForLoop ;Carry clear is success!
Failure:
Although this looks like a straight-forward implementation project, there
are several issues to consider. First, the call to Range_Resume
above looks simple enough, but there is no fixed address that corresponds
to the resume address. While it is certainly true that this Range
example has only one resume address, in general you can have as many yield
statements as you like in an iterator. For example, the following iterator
returns the values 1, 2, 3, and 4: OneToFour:iterator:integer;
begin OneToFour;
yield 1;
yield 2;
yield 3;
yield 4;
end OneToFour;
The initial call would execute the yield 1; statement. The
first resumption would execute the yield 2; statement, the
second resumption would execute yield 3;, etc. Obviously there
is no single resume address the calling code can count on.yield statement
then resumption by the foreach statement continues execution
within the procedure or function that executed the yield. Second,
the semantics of an iterator require all local variables and parameters
to maintain their values until the iterator terminates. That is, yielding
does not deallocate local variables and parameters. Likewise, any return
addresses left on the stack (e.g., the call to a procedure or function that
executes the yield statement) must not be lost when a piece
of code yields and the corresponding foreach statement resumes
the iterator. In general, this means you cannot use the standard call and
return sequence to yield from or resume to an iterator because you have
to preserve the contents of the stack. iterator OneToFour:integer;
begin
yield 1;
yield 2;
yield 3;
yield 4;
end;
and call it in the main program as follows:for i in OneToFour do writeln(i);Professional Pascal would completely rearrange your code. Instead of turning the iterator into an assembly language function and call this function from within the for loop body, this code would turn the
for loop
body into a function, expand the iterator in-line (much like a macro) and
call the for loop body function on each yield.
That is, Professional Pascal would probably produce assembly language that
looks something like the following:; The following procedure corresponds to the for loop body
; with a single parameter (I) corresponding to the loop
; control variable:
ForLoopCode proc near
push bp
mov bp, sp
mov ax, [bp+4] ;Get loop control value and
puti ; print it.
putcr
pop bp
ret 2 ;Pop loop control value off stk.
ForLoopCode endp
; The follow code would be emitted in-line upon encountering the
; for loop in the main program, it corresponds to an in-line
; expansion of the iterator as though it were a macro,
; substituting a call for the yield instructions:
push 1 ;On 286 and later processors only.
call ForLoopCode
push 2
call ForLoopCode
push 3
call ForLoopCode
push 4
call ForLoopCode
This method for implementing iterators is convenient and produces relatively
efficient (fast) code. It does, however, suffer from a couple drawbacks.
First, since you must expand the iterator in-line wherever you call it,
much like a macro, your program could grow large if the iterator is not
short and you use it often. Second, this method of implementing the iterator
completely hides the underlying logic of the code and makes your assembly
language programs difficult to read and understand.yield statement) and a dynamic
link, which is a pointer to the iterator's activation record. Typically
the dynamic link is just the value in the bp register at the
time you execute the yield instruction. This version implements
the four parts of an iterator as follows:call instruction for the initial iterator call,
call instruction for the yield statement,
ret instruction for the resume operation, and
ret instruction to terminate the iterator.
As an example, consider the Range iterator presented earlier.
This iterator requires two parameters, a starting value and an ending value:
foreach i in Range(1,10) do writeln(i);The code to make the initial call to the
Range iterator, producing
a stack like the one above, could be the following: push 1 ;Push start parameter value.
push 10 ;Push stop parameter value.
push offset ForDone ;Push termination address.
call Range ;Pushes yield return address.
ForDone is the first statement immediately following the foreach loop, that
is, the instruction to execute when the iterator returns failure. The foreach
loop body must begin with the first instruction following the call to Range.
At the end of the foreach loop, rather than jumping back to the start of
the loop, or calling the iterator again, this code should just execute a
ret instruction. The reason will become clear in a moment. So the implementation
of the above foreach statement could be the following: push 1 ;Obviously, this requires a
push 10 ; 80286 or later processor.
push offset ForDone
call Range
mov bp, [bp] ;Explained a little later.
puti
putcr
ret
ForDone:
Granted, this doesn't look anything at all like a loop. However, by playing
some major tricks with the stack, you'll see that this code really does
iterate the loop body (puti and putcr) as intended.Range_Start equ word ptr <[bp+8]> ;Address of Start parameter.
Range_Stop equ word ptr <[bp+6]> ;Address of Stop parameter.
Range_Yield equ word ptr <[bp+2]> ;Yield return address.
Range proc near
push bp
mov bp, sp
RangeLoop: mov ax, Range_Start ;Get start parameter and
cmp ax, Range_Stop ; compare against stop.
ja RangeDone ;Terminate if start > stop
; Okay, build the resume frame:
push bp ;Save dynamic link.
call Range_Yield ;Do YIELD operation.
pop bp ;Restore dynamic link.
inc Range_Start ;Bump up start value
jmp RangeLoop ;Repeat until start > stop.
RangeDone: pop bp ;Restore old BP
add sp, 2 ;Pop YIELD return address
ret 4 ;Terminate iterator.
Range endp
Although this routine is rather short, don't let its size deceive you; it's
quite complex. The best way to describe how this iterator operates is to
take it a few instructions at a time. The first two instructions are the
standard entry sequence for a procedure. Upon execution of these two instructions,
the stack looks like:
The next three statements in the Range iterator, at label
RangeLoop, implement the termination test of the while loop.
When the Start parameter contains a value greater than the
Stop parameter, control transfers to the RangeDone
label at which point the code pops the value of bp off the
stack, pops the yield return address off the stack (since this code will
not return back to the body of the iterator loop) and then returns via the
termination return address that is immediately above the yield return address
on the stack. The return instruction also pops the two parameters off the
stack.
The real work of the iterator occurs in the body of the while loop. The
push, call, and pop instructions
implement the yield statement. The push and call
instructions build the resume frame and then return control to the body
of the foreach loop. The call instruction is not calling a subroutine. What
it is really doing here is finishing off the resume frame (by storing the
yield resume address into the resume frame) and then it returns control
back to the body of the foreach loop by jumping indirect through
the yield return address pushed on the stack by the initial call to the
iterator. After the execution of this call, the stack frame looks like:
Also note that the ax register contains the return value
for the iterator. As with functions, ax is a good place to
return the iterator return result.
Immediately after yielding back to the foreach loop, the code
must reload bp with the original value prior to the iterator
invocation. This allows the calling code to correctly access parameters
and local variables in its own activation record rather than the activation
record of the iterator. Since bp just happens to point at the
original bp value for the calling code, executing the mov
bp, [bp] instruction reloads bp as appropriate. Of course,
in this example reloading bp isn't necessary because the body
of the foreach loop does not reference any memory locations off the bp
register, but in general you will need to restore bp.
At the end of the foreach loop body the ret instruction resumes
the iterator. The ret instruction pops the return address off
the stack which returns control back to the iterator immediately after the
call. The instruction at this point pops bp off the stack,
increments the Start variable, and then repeats the while loop.
Of course, this is a lot of work to create a piece of code that simply repeats
a loop ten times. A simple for loop would have been much easier and quite
a bit more efficient that the foreach implementation described in this section.
This section used the Range iterator because it was easy to
show how iterators work using Range, not because actually implementing
Range as an iterator is a good idea.